#!/usr/bin/python2
# -*- coding: UTF-8 -*-

def quick_sort(arr):
    if len(arr) < 2:    #基线条件，为空或只包含一个元素的数组（为有序的）
        return arr
    else:
        privot = arr[0]     #选择第一个元素作为基准值
        less = [i  for i in arr[1:] if i <= privot]   #由所有小于等于基准值的元素组成的子数组
        greater = [i for i in arr[1:] if i > privot]    #由所有大于基准值的元素组成的子数组
    return quick_sort(less) + [privot] + quick_sort(greater)

my_arr = [1, 4, 2, 10, 8, 3, 2, 9, 12]
print quick_sort(my_arr)
